//
// Created by liweimin on 2021/7/14.
//

#ifndef DATA_STRUCTURE_TREE_H
#define DATA_STRUCTURE_TREE_H

#endif //DATA_STRUCTURE_TREE_H

#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
//---------二叉树的顺序存储表示---------
#define MAX_TREE_SIZE 100
typedef int SqBiTree[MAX_TREE_SIZE];//0号存储单元存储根节点


//----------二叉树链式存储-二叉链表----------
#define DataType char

typedef struct BiNode
{
    DataType data;
    struct BiNode *left;
    struct BiNode *right;
} BiNode, *BiTree;


bool init(BiTree *biTree)
{
    if (biTree == NULL)
    {
        return false;
    }
    *biTree = NULL;
    return true;
}

void static input(BiTree *root)
{
    char ch;
    scanf("%c", &ch);
    if (ch == '#')
    {
        *root = NULL;
    } else
    {
        *root = (BiTree) malloc(sizeof(BiNode));
        if (!(*root))
        {
            exit(-1);
        }
        (*root)->data = ch;
        input(&(*root)->left);//构建左子树
        input(&(*root)->right);//构建右子树

    }
}

void create_tree(BiTree *root)
{
    printf("请输入二叉树的先序序列，如果没有子结点，使用#代替：\n");
    input(root);
}

void preorder(BiTree tree)
{
    if (tree)
    {
        printf("%c", tree->data);
        preorder(tree->left);
        preorder(tree->right);
    }
}

void inorder(BiTree tree)
{
    if (tree)
    {
        inorder(tree->left);
        printf("%c", tree->data);
        inorder(tree->right);
    }
}

void postorder(BiTree tree)
{
    if (tree)
    {
        postorder(tree->left);
        postorder(tree->right);
        printf("%c", tree->data);
    }
}


//----------------二叉树的二叉线索存储表示----------------
typedef enum
{
    Link, Thread
} PointerTag;//Link==0:指针，Thread==0:线索

typedef struct BiThrNode
{
    DataType data;
    struct BiThrNode *left, *right;
    PointerTag lTag, rTag;
} BiThrNode, *BiThrTree;


/* 全局变量 */
static BiThrTree pre;   // 指向当前访问结点的上一个结点（前驱）
/**
 * 中序遍历二叉线索树（非递归）
 * @param tree 
 * @param Visit 
 * @return 
 */
bool InOrderTraverse_Thr(BiThrTree tree, bool(*Visit)(DataType data))
{
    BiThrNode *p = tree->left;//tree 指向头结点，头结点的左链指向根节点
    while (p != tree)//空树或遍历结束
    {
        while (p->lTag == Link)p == p->left;//访问左子树
        if (!Visit(p->data)) return false;
        while (p->rTag == Thread && p->right != tree)
        {
            p = p->right;
            Visit(p->data);//访问后继结点
        }
        p = p->right;
    }
    return true;
}

static void InThread(BiThrTree t)
{
    if (t == NULL)return;
    InThread(t->left);//线索化左子树
    //左子树为空，需要建立前驱线索
    if (!t->left)
    {
        t->lTag = Thread;
        t->left = pre;
        /*
           * 如果左子树不为空，添加左孩子标记。
           * 教材中缺少这一步骤，这会导致出现一些幽灵BUG。
           * 这里的Link枚举值是零，如果编译器在动态分配内存后恰好把该标记初始化为0，
           * 那么效果跟手动设置Link是一样的。但如果编译器没有初始化零值，那么就会出BUG。
           */
    } else
    {
        t->lTag = Link;
    }
    // 如果前驱结点的右子树为空，则为前驱结点建立后继线索
    if (!pre->right)
    {
        pre->rTag = Thread;
        pre->right = t;

        /*
         * 如果右子树不为空，添加右孩子标记。
         * 教材中缺少这一步骤，这会导致出现一些幽灵BUG，理由同上。
         */
    } else
    {
        pre->rTag = Link;
    }

    pre = t;                // pre向前挪一步

    InThread(t->right);  // 线索化右子树
}

/**
 * 中序遍历建立中序二叉线索树
 * @param Bt
 * @param T
 * @return
 */
bool InOrderThreading(BiThrTree *Bt, BiThrTree T)
{
    if (!(Bt = (BiThrTree) malloc(sizeof(BiThrNode)))) return false;
    (*Bt)->lTag = Link, (*Bt)->data = '\0', (*Bt)->rTag = Thread;//建立头结点
    (*Bt)->right = (*Bt);//右指针回指
    if (!T)(*Bt)->left = (*Bt);//二叉树为空，左指针回指
    else
    {
        (*Bt)->left = T, pre = *Bt;
        InThread(T);//中序遍历，二叉线索化
        pre->right = *Bt;//最后一个结点指向头结点
        pre->rTag = Thread;//最后一个节点线索化
        (*Bt)->right = pre;//头结点指向最后一个结点，建立双向联系
    }
}